In recent years, the regulation for the protection of personal information or confidential information has been enhanced and the range of services using the personal or confidential information has widened. In addition, a hiding technique has been used which can utilize data while protecting personal information or confidential information. For example, there is a hiding technique which uses an encryption technique or a statistical technique depending on the type of data or a service requirement.
A homomorphic encryption technique has been known as the hiding technique using the encryption technique. The homomorphic encryption technique is an encryption technique which is one of the public key encryption methods using a pair of different keys in encryption and decryption and can operate encrypted data. For example, for plain texts m1 and m2, when an encryption function of the homomorphic encryption method related to addition or multiplication is E, the following Expressions (1) or (2) are established.E(m1)+E(m2)=E(m1+m2)  (1)E(m1)*E(m2)=E(m1*m2)  (2)
Expression (1) is referred to homomorphism for addition and Expression (2) is referred to homomorphism for multiplication.
When the homomorphic encryption method is used, the addition or multiplication of ciphertexts makes it possible to obtain a ciphertext, which is the addition or multiplication result, without decrypting the ciphertext. The properties of the homomorphic encryption are used in, for example, the field of electronic voting or electronic money or the field of cloud computing. Representative examples of the homomorphic encryption method include a Rivest-Shamir-Adleman (RSA) encryption method which is used for multiplication and an Additive ElGamal encryption method which is used for addition.
In recent years, a homomorphic encryption method which can be used for both addition and multiplication has been known. In addition, a homomorphic encryption method has been known which can be used for both addition and multiplication and is practical in terms of both a processing performance and the size of encrypted data.
Here, an example of the homomorphic encryption method will be described. First, three key generation parameters (n, q, t) are mainly prepared for the generation of an encryption key. Here, n is an integer raised to the second power and is called a lattice dimension, q is a prime number, and t is an integer less than the prime number q. In the procedure of an encryption key generation process, first, an n-dimensional polynomial sk having very small coefficients is generated at random with a secret key. The magnitude of each coefficient is limited by a given parameter σ. Then, an n-dimensional polynomial a1 having each coefficient less than q and an n-dimensional polynomial e having very small coefficients are generated at random.
Then, a0=−(a1*sk+t*e) is calculated and a set (a0, a1) is defined by a public key pk. When a polynomial of a0 is calculated, xn=−1, xn+1=−x, . . . are calculated for a polynomial of degree n or more to continuously calculate a polynomial of less than degree n. In addition, for the coefficients of the polynomial, the coefficient is divided by the prime number q and the remainder is output. In general, a space in which the above-mentioned calculation is performed is mathematically represented by Rq: =Fq[x]/(xn+1).
Then, for plain text data m represented by a polynomial of degree n in which each coefficient is less than t and a public key pk=(a0, a1), three polynomials u, f, and g of degree n in which each coefficient is very small are generated at random and the encrypted data E(m, pk)=(c0, c1) of the plain text data m is defined as follows. For (c0, c1), c0−a0*u+t*g+m and c1−a1*u+t*f are calculated. This calculation is also performed in the space Rq.
Then, for two ciphertexts E(m1, pk)=(c0, c1) and E(m2, pk)=(d0, d1), ciphertext addition E(m1, pk)+E(m2, pk) is calculated as (c0+d0, c1+d1) and ciphertext multiplication E(m1, pk)*E(m2, pk) is calculated as (c0+d0, c0*d1+c1*d0, c1*d1). When the ciphertexts are multiplied as described above, it is noted that the data size of the ciphertext changes from a 2-component vector to a 3-component vector.
Finally, a decryption process is performed. For a ciphertext c=(c0, c1, c2, . . . ) (here, it is assumed that the number of components of ciphertext data increases due to an encryption operation, such as a plurality of ciphertext multiplications), a secret key sk is used to calculate Dec(c, sk)=[c0+c1*sk+c2*sk+ . . . ]q mod t. In this way, decryption is performed. Here, for the value of [z]q, a remainder w when an integer z is divided by q is calculated. When w<q is satisfied, [z]q=w is output. When w≧q is satisfied, [z]q=w−q is output. In addition, “a mod t” means the remainder when the integer a is divided by t.
Next, the following numerical example is given for ease of understanding:Secret key sk=Mod(Mod(4,1033)*x3+Mod(4,1033)*x2+Mod(1,1033)*x,x4+1);Public key pk=(a0,a1),a0=Mod(Mod(885,1033)*x3+Mod(519,1033)*x2+Mod(621,1033)*x+Mod(327,1033),x4+1), anda1=Mod(Mod(661,1033)*x3+Mod(625,1033)*x3+Mod(861,1033)*x+Mod(311,1033),x4+1); andE(m,pk)=(c0,c1),Plain text data m=3+2x+2x2+2x3,c0=Mod(Mod(822,1033)*x3+Mod(1016,1033)*x2+Mod(292,1033)*x+Mod(243,1033),x4+1), andc1=Mod(Mod(840,1033)*x3+Mod(275,1033)*x3+Mod(628,1033)*x+Mod(911,1033),x4+1).
In the above-mentioned values, the key generation parameters (n, q, t) are set to (4, 1033, 20). In addition, Mod(a, q) means the remainder when the integer a is divided by the prime number q and Mod(f(x), x4+1) means a polynomial of the remainder when a polynomial f(x) is divided by a polynomial x4+1. However, for example, it is assumed that Mod(f(x), x4+1) means x4=−1, x5=x, . . . .
An application example of the homomorphic encryption method is hidden pattern matching. The hidden pattern matching will be described with reference to FIG. 6. FIG. 6 is a diagram illustrating pattern matching. First, pattern matching is a process of determining whether a pattern string is included in a text string and is, for example, a process of determining whether a pattern string P=“abbac” is included in a text string T=“acbabbaccb”.
In this case, as illustrated in FIG. 6, the number where the text is matched with the pattern is calculated while the pattern string is shifted one character by one character relative to the text string T. In FIG. 6, the number of characters matched with each other is referred to as a score vector. Here, a plurality of distances which are referred to as the score vector are calculated. In this example, since the length of the pattern string P is 5, the text and the pattern are matched with each other at the position of a component with a score vector value of 5. As such, in the pattern matching without encryption, for the text string T and the pattern string P, the distance between the text string and the pattern string P is calculated while the pattern string P is shifted one character by one character.
In the hidden pattern matching using homomorphic encryption, a plurality of distances are calculated, with the text string T and the pattern string P encrypted by homomorphic encryption. Here, as illustrated in FIG. 6, a hidden pattern matching operation model among the three parties, that is, an information registrant having the text string T, a collator having the pattern string P, and a cloud which calculates an encryption distance in the hidden pattern matching is considered.
First, the collator generates a public key and a secret key for generating a homomorphic encryption key and opens only the public key to the public. Here, the collator opens the public key to the information registrant and the cloud. Then, the information registrant encrypts its own text string T with the public key transmitted from the collator, using homomorphic encryption, and stores the encrypted text E(T) in a database of the cloud.
The collator performs homomorphic encryption on the pattern string P and transmits only the encrypted pattern E(P) to the cloud, in order to collate whether the pattern string P is present. The cloud calculates a plurality of distances between the encrypted text E(T) and the encrypted pattern E(P) while encrypting the distances and transmits only the encryption result to the collator. The collator can decrypt the encryption result transmitted from the cloud with its own secret key and determine whether the pattern P is included in the text T on the basis of the decryption result.    Patent Document 1: Japanese Laid-open Patent Publication No. 2000-181486    Patent Document 2: Japanese Laid-open Patent Publication No. 2009-271584    Non-patent Document 1: C. Gentry, “Fully Homomorphic encryption using ideal lattices”, STOC 2009, ACM, pp. 169-178, 2009    Non-patent Document 2: K. Lauter, M. Naehrig and V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011
In the hidden pattern matching using the above-mentioned cloud, since all processes are performed on the cloud, with data being encrypted, data for the information registrant and the collator is not disclosed. Therefore, it is possible to outsource a pattern matching process even in an environment such as cloud with poor security.
Meanwhile, since hidden pattern matching is performed with data being encrypted, only the application of the homomorphic encryption method to the pattern matching is not practical in terms of the amount of data or an operation load and it takes a lot of time for the process.
Detailed application examples of the above-mentioned cloud hidden pattern matching include concealed information search, such as keyword or web search, concealed DNA analysis which is used in criminal investigation or the determination of blood relationship, and a concealed genetic test which is used in an obese genetic test or infection examination.